/**
 * rcpsp.cpp
 *
 *  Created on: 04/06/2013
 *      Author: gilvan
 */

#include <iostream>
#include <vector>
#include <set>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <queue>
#include <time.h>
#include <math.h>
#include <map>
#include <stack>
#include <sys/time.h>
#include <pthread.h>

using namespace std;

struct Node {
    int                 LB;
    set<int>            S;
    set<int>            PS;
    set<int>            C;
    vector<int>         F;
    vector<int>         s;
    vector<set<int> >   sucss;
    vector<set<int> >   preds;
};
struct Task {
	int id;
	int pt;
	int* dmds;
	set<int>* succs;
	set<int>* preds;
};

/**
 * Globals Variables
 */
int     NbTasks, NbRsrcs, FileType;
int     *Capacity;
Task    *Tasks;
char    *FileName;
char    *OutputFileName;
FILE    *out;

/**
 * Functions IO
 */
ostream &operator << ( std::ostream& ostrm, vector<int> &list);
ostream &operator << ( std::ostream& ostrm, Node *No);
ostream &operator << ( std::ostream& ostrm, set<int> &list);
void    Parse_Arguments(int argc, char **argv);
void    Usage(char *opt);
void    Predecessors();
void    Free();
void    Print_Params();
int     Read_Psp_File(char* fileName);
int     Read_Cplex_File(char* fileName);
int     Read_TUClausthal(char* fileName);


#define inf 999999999

int T;
Node BestSolution;
Node Raiz;
int NbThreads = 2;

int threads_in_cond_wait = 0;
stack<Node> new_stack;
pthread_cond_t term_cond_var = PTHREAD_COND_INITIALIZER ;
pthread_mutex_t term_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t best_solution_mutex = PTHREAD_MUTEX_INITIALIZER;


#define INV -1
#define MAX 100


/**
 * Functions to Branch and Bound Algorithm
 */

void Cut_Set(Node *No, int task)
{
    
    set<int>::iterator j, k, w;
    int max = 0;
    
    for (j = No->sucss[task].begin(); j != No->sucss[task].end(); j++) // quais dos sucessores do i
    {
        bool isB = true;
        max = 0;
        for(k = No->preds[*j].begin(); k != No->preds[*j].end() && isB; k++) // tem todos os predecessores em no schedule
        {
            if (No->PS.find(*k) == No->PS.end())
            {
                isB = false;
            } else if(max < No->F[*k])
            {
                max = No->F[*k];
            }
        }
        if(isB)
        {
            No->C.insert(*j);
            No->s [ *j ] = max;
        }
    }
    
    
}

/**
 * Implementation of The Critical Path Method
 * From Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne - 4.4 Shortest Paths
 */

int Critical_Path (Node *No)
{
    
    vector<bool> visited (NbTasks+1, false);
    vector<int> dist (NbTasks+1, inf);
    set<int>::iterator it, itEnd;
    
    int at = 1;
    dist[at] = 0;
    int iterations = NbTasks;
    for (int q = 0 ; q < iterations ; q++)
    {
        visited [ at ] = true;
        
        it = No->sucss[at].begin();
        itEnd = No->sucss[at].end();
        
        while(it != itEnd)
        {
            if(dist[(*it)] > (dist[at] + (-Tasks[(*it)-1].pt)))
            {
                dist[(*it)] = dist[at] + (-Tasks[(*it)-1].pt);
            }
            it++;
        }
        
        int max = inf;
        for (int k = 2 ; k <= NbTasks ; k++)
        {
            if(!visited[k] && max > dist[k])
            {
                at = k;
                max = dist[k];
            }
        }
    }
    
    return -dist[NbTasks];
    
}

int Early_Finish(Node *No)
{
    
    set<int>::iterator it, itEnd;
    vector<int>::iterator q;
    int min = inf;
    vector<int> temp ( No->S.begin(), No->S.end());
    for (it = No->S.begin(); it != No->S.end(); it++)
    {
        if(min > No->F[*it])
        {
            min = No->F[*it];
        }
    }
    
    // removendo atividades
    for (q = temp.begin(); q != temp.end(); q++)
    {
        if(min == No->F[*q])
        {
            No->S.erase(*q);
        }
    }
    
    return min;
}

set<int> Elegible_Tasks(Node *No, int m)
{
    
    set<int>::iterator i;
    set<int> E;
    for (i = No->C.begin(); i != No->C.end(); i++)
    {
        if (No->s[*i] <= m)
        {
            E.insert(*i);
        }
    }
    
    return E;
}

void Parallel_Partners(Node *No, int task, int &counter, int &partner)
{
    
    set<int>::iterator k;
    counter = 0;
    
    // calcular recursos disponíveis
    vector<int> usage (Capacity, Capacity + NbRsrcs); // cópia do vetor recursos
    for(int r = 0 ; r < NbRsrcs; r++)
    {
        usage [ r ] -= Tasks[task-1].dmds[r];
        for(k = No->S.begin(); k != No->S.end(); k++)
        {
            usage [ r ] -= Tasks[(*k)-1].dmds[r];
        }
        if(usage[r] < 0)
        {
            return;
        }
    }
    
    counter = 1;
    
    
    for( int tsk = 1 ; tsk <= NbTasks; tsk++)
    {
        if(task != tsk && No->PS.find(tsk) == No->PS.end() && No->preds[tsk].find(task) == No->preds[tsk].end()) // task ainda não foi escalonada
        {
            bool isReady = true;
            for(k =  No->preds[tsk].begin(); k !=  No->preds[tsk].end() && isReady; k++) // tem todos os predecessores em no schedule
            {
                if (No->PS.find(*k) == No->PS.end() || No->S.find(*k) != No->S.end()) // caso não esteja no schedule ou esteja em processamento
                {
                    isReady = false;
                }
            }
            
            
            if(isReady)
            {
                
                // calcular recursos disponíveis
                vector<int> usage (Capacity, Capacity + NbRsrcs); // cópia do vetor recursos
                for(k = No->S.begin(); k != No->S.end(); k++)
                {
                    for(int r = 0 ; r < NbRsrcs; r++)
                    {
                        usage [ r ] -= Tasks[(*k)-1].dmds[r];
                    }
                }
                
                bool isPartner = true;
                for(int r = 0 ; r < NbRsrcs && isPartner; r++)
                {
                    if ( usage [ r ] - (Tasks[tsk-1].dmds[r] + Tasks[task-1].dmds[r]) < 0 )
                    {
                        isPartner = false;
                    }
                }

                if (isPartner)
                {
                    counter++;
                    partner = tsk;
                    
                }
            }
        }
    }
    
}

vector<set<int> > Delaying_Set(Node *No, vector<int> &Usage)
{
    
    set<int> tempS = No->S;
    set<int> Dq;
    int nS = (int) No->S.size();
    set<int>::iterator i, j, k;
    vector<set<int> > D;
    
    int nQ = 0;
    for (int ahead = 1; ahead <= nS; ahead++)
    {
        
        for (i = tempS.begin(); i != tempS.end(); i++)
        {
            int size = 0;
            Dq.clear();
            for (j = i; j != tempS.end() && size < ahead; j++)
            {
                Dq.insert(*j);
                size++;
            }
            
            bool hasResources = true;
            vector<int> tU = Usage;
            
            for(int r = 0 ; r < NbRsrcs && hasResources; r++)
            {
                for(k = Dq.begin(); k != Dq.end(); k++)
                {
                    tU [ r ] += Tasks[(*k)-1].dmds[r];
                }
                
                if (tU [ r ] < 0 )
                {
                    hasResources = false;
                }
                
            }
            
            if(hasResources)
            {
                bool isIn = false;
                for (int w = 0 ; w < nQ && !isIn; w++)
                {
                    set<int> temp = Dq;
                    int size = (int) temp.size();
                    temp.insert(D[w].begin(), D[w].end());
                    if ( size == temp.size())
                    {
                        isIn = true;
                    }
                }
                
                if(!isIn)
                {
                    nQ++;
                    D.push_back(Dq);
                }
            }
        }
        
        if (ahead == 1)
        {
            for (int w = 0 ; w < nQ; w++)
            {
                tempS.erase(*D[w].begin());
            }
        }
    }
    
    
    
    return D;
}

bool compare(const Node &a, const Node &b)
{
    return a.LB > b.LB;
}

void Initialize_Node(Node *No)
{
    
    No->F.resize ( NbTasks+1, inf );
    No->s.resize ( NbTasks+1, inf );
    
    No-> F [ 0 ] = inf;
    No-> F [ 1 ] = 0;
    No->PS.insert(1);
    No->S.insert(1);
    
    No->sucss.resize(NbTasks+1);
    No->preds.resize(NbTasks+1);
    
    // inicializar sucessores e predecessores
    for (int i = 0; i < NbTasks; i++)
    {
        No->sucss[i+1] = *(Tasks[i].succs);
        No->preds[i+1] = *(Tasks[i].preds);
    }
    
    Cut_Set( No, 1);
    
    No->LB  = Critical_Path(No);
    
}

void Copy_Node(Node *orig, Node *dest)
{
    dest->F = orig->F;
    dest->s = orig->s;
    dest->PS = orig->PS;
    dest->S = orig->S;
    dest->LB = orig->LB;
    dest->C  = orig->C;
    
    dest->sucss = orig->sucss;
    dest->preds = orig->preds;
    
}

void Branches (Node *No, vector<int> Usage, stack<Node> *stack)
{
    
    vector<set<int> > D = Delaying_Set (No, Usage);
    vector<Node> Branches;
    
    set<int>::iterator i, j;
    
    for (int w = 0 ; w < D.size(); w++)
    {
        int menor = inf;
        int task = inf;
        
        for(i = No->S.begin(); i != No->S.end(); i++)
        {
            if(D[w].find(*i) == D[w].end() && No->F[*i] < menor)
            {
                task = *i;
                menor = No->F[*i];
            }
        }
        
        Node new_one;
        Copy_Node(No, &new_one);
        
        new_one.C.insert(D[w].begin(), D[w].end());
        
        for(i = D[w].begin(); i != D[w].end(); i++)
        {
            new_one.S.erase(*i);
            new_one.PS.erase(*i);
            new_one.sucss[task].insert(*i);
            new_one.preds[*i].insert(task);
            new_one.F [*i] = inf;
            new_one.s [*i] = menor;
            
            for ( j = new_one.sucss[*i].begin(); j != new_one.sucss[*i].end(); j++)
            {
                new_one.C.erase(*j);
                new_one.s [ *j ] = inf;
            }
        }
        
        int L = Critical_Path ( &new_one );
        
        if (L > new_one.LB)
        {
            new_one.LB = L;
        }
        
        Branches.push_back(new_one);
        
    }
    
    sort(Branches.begin(), Branches.end(), compare);
    
    for (int t = 0; t < Branches.size(); t++)
    {
        if (Branches[t].LB < T) stack->push(Branches[t]);
    }
    
}

bool Terminated(stack<Node> *stack)
{
    if ( stack->size() > 2 && threads_in_cond_wait && new_stack.empty() ) /* have work to split, threads waiting and last shared work was consumed */
    {
        pthread_mutex_lock ( &term_mutex );
        if ( threads_in_cond_wait && new_stack.empty() )
        {
            int half = (int) stack->size() / 2;
            while ( new_stack.size() < half )
            {
                new_stack.push(stack->top());
                stack->pop();
            }
            pthread_cond_signal( &term_cond_var );
        }
        pthread_mutex_unlock ( &term_mutex );
        return false;
    } else if (!stack->empty()) /* stack not empty, keep with the good work */
    {
        return false;
    } else /* my stack is empty, somebody send me work */
    {
        pthread_mutex_lock ( &term_mutex );
        if ( threads_in_cond_wait == NbThreads - 1 ) /* last thread running */
        {
            threads_in_cond_wait++;
            pthread_cond_broadcast(&term_cond_var);
            pthread_mutex_unlock ( &term_mutex );
            return true;
        } else /* somebody is still working, lets wait */
        {
            threads_in_cond_wait++;
            while (pthread_cond_wait ( &term_cond_var, &term_mutex ) != 0 );
            /* we been awakened ihuuuuuu */
            if ( threads_in_cond_wait < NbThreads ) /* yep, we have work to do */
            {
                (*stack) = new_stack;
                while(!new_stack.empty()) new_stack.pop();
                threads_in_cond_wait--;
                pthread_mutex_unlock ( &term_mutex );
                return false;
            } else /* all threads are done */
            {
                pthread_mutex_unlock ( &term_mutex );
                return true;
            }
        } /* end else somebody is still working */
    } /* end else my stack is empty */
    
}

void Insert_Task ( Node *No, int task, int m)
{
    No->S.insert(task);
    No->PS.insert(task);
    No->C.erase(task);
    No->F [ task ] = Tasks[task-1].pt + m ;
    No->s [ task ] = inf;
    Cut_Set(No, task);
}

void UpdateBest (Node *No)
{
    pthread_mutex_lock ( &best_solution_mutex );
    if ( T > No-> F [ NbTasks] )
    {
        T = No-> F [ NbTasks];
        BestSolution = (*No);
    }
    pthread_mutex_unlock ( &best_solution_mutex);
}
void *Local_Branch_And_Bound(void *args)
{
    /* LOCAL VARIABLES */
    int rank = *(int*) args;
    stack<Node> local_stack;
    
    /* THE THREAD ZERO HAS THE FIRST NODE */
    if ( rank == 1)
    {
        local_stack = new_stack;
        new_stack.pop();
    }
    
    //printf("# Thread %d Has Begun\n", rank);
    
    Node act;
    Node *No = new Node;
    bool hasConflict;
    int m;
    set<int> E;
    set<int>::iterator i, j;
    int counter, partner;
    bool hasInserted = false;
    
    int NodesCount = 0;
    while (!Terminated(&local_stack))
    {
        
        /* GET THE TOP OF QUEUE */
        (*No) = local_stack.top();
        
        /* POP THE TOP OF THE STACK */
        local_stack.pop();
        
        if ( No->LB < T ) /* IF LOWER BOUND IS BEST THEM THE INCUMBENT */
        {
			NodesCount++;
			
            hasConflict = false;
            while ( !hasConflict ) /* WHILE NOT HAPPEN RESOURCES CONFLICT */
            {
                /* CALCULATE NEW TIME AND ELEGIBLE TASKS */
                E.clear();
                m = 0;
                while ( E.empty() && m < T )
                {
                    m = Early_Finish(No);
                    E = Elegible_Tasks(No, m);
                }
                
                if ( m == inf )
                {
                    printf("Error: wrong value of m");
                    exit(1);
                }
                
                /* TRY TO INSERT ELEGIBLE TASKS */
                hasInserted = false;
                for ( i = E.begin(); i != E.end() && !hasInserted; i++)
                {
                    Parallel_Partners( No, *i, counter, partner);
                    if ( counter == 1 )
                    {
                        Insert_Task ( No, *i, m) ;
                        if( *i == NbTasks )
                        {
                            if( T > No->F[NbTasks] )
                            {
                                UpdateBest (No);
                                //printf("Try Update Solution = %d\t by Thread %d\n", No->F[NbTasks], rank);
                            }
                            hasConflict = true;
                        }
                        hasInserted = true;
                    } /* END IF COUNTER == 1 */
                } /* END FOR ELEGIBLE TASKS */
                
                if ( !hasInserted ) /* IF NONE TASK HAS BEEN INSERTED */
                {
                    /* INSERT ALL ELEGIBLE TASKS */
                    for ( i = E.begin(); i != E.end() && !hasInserted; i++)
                    {
                        Insert_Task ( No, *i, m) ;
                    }
                    
                    /* VERIFY IF HAPPEN CONFLICT WITH RESOURCES */
                    vector<int> Usage (Capacity, Capacity + NbRsrcs);
                    
                    for(int r = 0 ; r < NbRsrcs; r++)
                        for(i = No->S.begin(); i != No->S.end(); i++)
                            Usage [ r ] -= Tasks[(*i)-1].dmds[r];
                    
                    for(int r = 0 ; r < NbRsrcs && !hasConflict; r++)
                    {
                        if ( Usage [ r ] < 0 )
                        {
                            hasConflict = true;
                        }
                    }
                    
                    if ( hasConflict ) /* IF HAS CONFLIT WITH RESOURCES, CREATE BRANCHES */
                    {
                        Branches( No , Usage, &local_stack );
                    }
                    
                } /* END IF NONE TASK HAS BEEN INSERTED */
            } /* END WHILE NOT HAPPEN RESOURCES CONFLICT */
        } /* END IF LOWER BOUND IS BEST THEM THE INCUMBENT */
    } /* WHILE NOT TERMINATED */
    
    //printf("# Thread %d Has Processed %d Nodes\n", rank, NodesCount );
    
    int *c = (int*) args;
    (*c) = NodesCount;
    
    return (NULL);
}

void Init_Parallel()
{
    
    /* create first node and insert first task */
    Initialize_Node(&Raiz);
    
    /* initialize incumbent */
    T = inf;
    
    /* insert first node in the global stack */
    new_stack.push(Raiz);
    
    /* create threads */
    pthread_t *threads = new pthread_t [ NbThreads ];
    int *ranks = new int [ NbThreads ];
    
    for ( int i = 0; i < NbThreads; i++ )
    {
        ranks [ i ] = i + 1;
        pthread_create( &threads[i], NULL, Local_Branch_And_Bound, &ranks [ i ] );
    }
    
    for ( int i = 0; i < NbThreads; i++ )
    {
        pthread_join(threads[i], NULL);
    }
    
    int Total = 0;
    for ( int i = 0; i < NbThreads; i++ )
    {
        Total += ranks [ i ] ;
    }
    fprintf( out, "\nParallel Best Solution: %d \n", T );
    fprintf( out, "# Nodes Evaluated: %d \n", Total );
    fprintf( out, "Schedule = { \n");
    for ( int k = 1 ; k <= NbTasks; k++)
    {
        fprintf(out, "\tTask: %5d \tBegin: %5d \tEnd: %5d\n", k, BestSolution.F[k]-Tasks[k-1].pt, BestSolution.F[k]);
    }
    fprintf(out, "};\n");
    
    delete [] threads;
    delete [] ranks;
}

void Serial_Branch_And_Bound()
{
    
    /* create first node and insert first task */
    Initialize_Node(&Raiz);
    
    /* initialize incumbent */
    T = inf;
    
   if (Raiz.LB == -inf)
   {
       printf("Lower Bound Error.\n");
       exit(1);
   }
    
    stack<Node> local_stack;
    /* insert first node in the global stack */
    local_stack.push(Raiz);
    
    Node act;
    Node *No = new Node;
    bool hasConflict;
    int m;
    set<int> E;
    set<int>::iterator i, j;
    int counter, partner;
    bool hasInserted = false;
    
    int NodeCounter = 0;
    
    while (!local_stack.empty())
    {
        /* GET THE TOP OF QUEUE */
        (*No) = local_stack.top();
        
        /* POP THE TOP OF THE STACK */
        local_stack.pop();
        
        if ( No->LB < T ) /* IF LOWER BOUND IS BEST THEM THE INCUMBENT */
        {
            NodeCounter++;
            
            hasConflict = false;
            while ( !hasConflict ) /* WHILE NOT HAPPEN RESOURCES CONFLICT */
            {
                /* CALCULATE NEW TIME AND ELEGIBLE TASKS */
                E.clear();
                m = 0;
                while ( E.empty() && m < T )
                {
                    m = Early_Finish(No);
                    E = Elegible_Tasks(No, m);
                    //cout << E << endl;
                }
                
                if ( m == inf )
                {
                    
                    printf("Error: wrong value of m.\n");
                    //cout << No;
                    exit(1);
                }
                
                /* TRY TO INSERT ELEGIBLE TASKS */
                hasInserted = false;
                for ( i = E.begin(); i != E.end() && !hasInserted; i++)
                {
                    Parallel_Partners( No, *i, counter, partner);
                    if ( counter == 1 )
                    {
                        Insert_Task ( No, *i, m) ;
                        if( *i == NbTasks )
                        {
                           // printf("Feasible Solution = %d\n", No->F[NbTasks]);
                            if( T > No->F[NbTasks] )
                            {
                             //   printf("Update Solution = %d\n", No->F[NbTasks]);
                                BestSolution = (*No);
                                T = No->F[NbTasks];
                            }
                            hasConflict = true;
                        }
                        hasInserted = true;
                    } /* END IF COUNTER == 1 */
                } /* END FOR ELEGIBLE TASKS */
                
                if ( !hasInserted ) /* IF NONE TASK HAS BEEN INSERTED */
                {
                    /* INSERT ALL ELEGIBLE TASKS */
                    for ( i = E.begin(); i != E.end() && !hasInserted; i++)
                    {
                        Insert_Task ( No, *i, m) ;
                    }
                    
                    /* VERIFY IF HAPPEN CONFLICT WITH RESOURCES */
                    vector<int> Usage (Capacity, Capacity + NbRsrcs);
                    
                    for(int r = 0 ; r < NbRsrcs; r++)
                        for(i = No->S.begin(); i != No->S.end(); i++)
                            Usage [ r ] -= Tasks[(*i)-1].dmds[r];
                    
                    for(int r = 0 ; r < NbRsrcs && !hasConflict; r++)
                    {
                        if ( Usage [ r ] < 0 )
                        {
                            hasConflict = true;
                        }
                    }
                    
                    if ( hasConflict ) /* IF HAS CONFLIT WITH RESOURCES, CREATE BRANCHES */
                    {
                        Branches( No , Usage, &local_stack );
                    }
                    
                } /* END IF NONE TASK HAS BEEN INSERTED */
            } /* END WHILE NOT HAPPEN RESOURCES CONFLICT */
        } /* END IF LOWER BOUND IS BEST THEM THE INCUMBENT */
    } /* WHILE NOT TERMINATED */
    
    
    fprintf( out, "\nSerial Best Solution: %d \n", T );
    fprintf( out, "# Nodes Evaluated: %d \n", NodeCounter );
    fprintf( out, "Schedule = { \n");
    for ( int k = 1 ; k <= NbTasks; k++)
    {
        fprintf( out, "\tTask: %5d \tBegin: %5d \tEnd: %5d\n", k, BestSolution.F[k]-Tasks[k-1].pt, BestSolution.F[k]);
    }
    fprintf( out,"};\n");
    
}

struct timeval start_time, end_time;

double tempo()
{
	gettimeofday(&end_time, NULL);
	
	double run_time = ((end_time.tv_sec  - start_time.tv_sec) * 1000000u + end_time.tv_usec - start_time.tv_usec) / 1.e6;
	
	start_time = end_time;
	
	return run_time;
}

/**
 * Principal
 */
int main(int argc, char **argv)
{
    
	/*
     * Initializing variables
     */
	FileType = 0;
	FileName = 0;
    
	/*
     * Parsing comand lines parameters
     */
	Parse_Arguments(argc, argv);
    
	/*
     * Check Parameters
     */
	if (!FileName || !FileType)
	{
		Usage(argv[0]);
	}
    
	/*
     * Reading Input
     */
	switch(FileType)
	{
		case 1:
            Read_Cplex_File(FileName);
            break;
            
		case 2:
            Read_Psp_File(FileName);
            break;
        case 3:
            Read_TUClausthal(FileName);
            break;
	}
    
    /*
     * Calculate Predecessors
     */
	Predecessors();
	
    out = fopen ( OutputFileName , "a");
    if (out == NULL) perror ("Error opening output file");
    fprintf( out, "Entrada: %s\n", FileName);
    
	/*
     * Show Input Data
     */
	
    //Print_Params();
    
    gettimeofday(&start_time, NULL);
    Serial_Branch_And_Bound();
    double serial = tempo();
  
    gettimeofday(&start_time, NULL);
    Init_Parallel();
	double parallel = tempo();
	
    printf("Serial Time: %.2f seconds \t", serial );
    printf("Paralell Time: %.2f seconds\t Speedup: %.2f\n\n", parallel, serial/parallel);
    
    fprintf( out, "\nSerial Time: %.2f seconds \t", serial );
    fprintf( out, "Paralell Time: %.2f seconds\t Speedup: %.2f\n\n", parallel, serial/parallel);
    
    
    /*
     * Free Memory
     */
	Free();
    
}

/**
 * Read a Cplex Input File
 */
int Read_Cplex_File(char* fileName)
{
    
	FILE* input = fopen(fileName, "r");
	fscanf(input, "NbTasks = %d;\n", &NbTasks);
	fscanf(input, "NbRsrcs = %d;\n", &NbRsrcs);
	fscanf(input, "Capacity = [ ");
    
	Capacity = (int*) malloc(sizeof(int)*NbRsrcs);
	if(!Capacity)
		return -1;
    
	for(int i=0; i<NbRsrcs; i++)
		fscanf(input, "%d, ", &Capacity[i]);
	fscanf(input, " ]; ");
    
	Tasks = (Task*) malloc(sizeof(Task)*NbTasks);
	if(!Tasks)
		return -1;
    
	fscanf(input, "Tasks = {\n");
	for(int i=0; i<NbTasks; i++) {
		Tasks[i].dmds =  (int*) malloc(sizeof(int)*NbRsrcs);
        
		fscanf(input, "  < %d, %d, [ ", &Tasks[i].id, &Tasks[i].pt);
        
		int j=0;
		while(j<NbRsrcs-1)
			fscanf(input, "%d, ", &Tasks[i].dmds[j++]);
		fscanf(input, "%d ], { ", &Tasks[i].dmds[j]);
        
		int aux;
		std::set<int>* sp = new std::set<int>();
		while(fscanf(input, "%d, ", &aux) == 1)
			sp->insert(aux);
		fscanf(input, "} >,");
        
		Tasks[i].succs = sp;
	}
    
	return 0;
    
}

/**
 * Read a file from PSPLib
 */
int Read_Psp_File(char* fileName)
{
    
	FILE* input = fopen(fileName, "r");
	char s[300];
	int n, aux;
	fscanf(input, "%[^j]j%[^j]j%[^j]jobs (incl. supersource/sink ):  %d;\n", s, s, s, &NbTasks);
	fscanf(input, "%[^R]%[^r]renewable                 :  %d;\n", s, s, &NbRsrcs);
	fscanf(input, "%[^#]#%[^#]#%[^#]#%[^\n]\n", s, s, s, s);
    
	Tasks = (Task*) malloc(sizeof(Task)*NbTasks);
	if(!Tasks)
		return -1;
    
	Capacity = (int*) malloc(sizeof(int)*NbRsrcs);
	if(!Capacity)
		return -1;
    
    
	for(int i=0; i<NbTasks; i++) {
		fscanf(input, "%d %d %d ",  &Tasks[i].id, &n, &n);
        
		std::set<int>* sp = new std::set<int>();
		for(int j=0; j<n; j++) {
			fscanf(input, "%d ", &aux);
			sp->insert(aux);
		}
		Tasks[i].succs = sp;
	}
    
	fscanf(input, "%[^-]%s\n", s, s);
	for(int i=0; i<NbTasks; i++) {
		fscanf(input, "%d %d %d ",  &n, &n, &Tasks[i].pt);
		Tasks[i].dmds =  (int*) malloc(sizeof(int)*NbRsrcs);
		for(int j=0; j<NbRsrcs; j++) {
			fscanf(input, "%d ", &Tasks[i].dmds[j]);
		}
	}
    
	fscanf(input, "%[^:]: %[^\n]", s, s);
    
	for(int i=0; i<NbRsrcs; i++) {
		fscanf(input, "%d ", &Capacity[i]);
	}
    
	return 0;
    
}

int Read_TUClausthal(char* fileName)
{
    
	FILE* input = fopen(fileName, "r");
	int n, aux;
	fscanf(input, "%d %d 0 0\n", &NbTasks, &NbRsrcs);
    
    NbTasks += 2;
	Tasks = (Task*) malloc(sizeof(Task)*NbTasks);
	if(!Tasks)
		return -1;
    
	Capacity = (int*) malloc(sizeof(int)*NbRsrcs);
	if(!Capacity)
		return -1;
    
	for(int i=0; i<NbTasks; i++) {
		fscanf(input, "%d 1 %d ",  &Tasks[i].id, &n);
        
        Tasks[i].id++;
        
		std::set<int>* sp = new std::set<int>();
        std::vector<int> tmp ( n, -1);
		for(int j=0; j<n; j++) {
			fscanf(input, "%d ", &aux);
            tmp [ j ] = aux+1;
		}
		
		for(int j=0; j<n; j++) {
			fscanf(input, "[%d] ", &aux);
            if ( aux >= 0 )
            {
                sp->insert(tmp[j]);
            }
		}
        Tasks[i].succs = sp;
	}
    
	for(int i=0; i<NbTasks; i++) {
		fscanf(input, "%d %d %d ",  &n, &n, &Tasks[i].pt);
		Tasks[i].dmds =  (int*) malloc(sizeof(int)*NbRsrcs);
		for(int j=0; j<NbRsrcs; j++) {
			fscanf(input, "%d ", &Tasks[i].dmds[j]);
		}
	}
    
	for(int i=0; i<NbRsrcs; i++) {
		fscanf(input, "%d ", &Capacity[i]);
	}
    
    for(int i=1; i<NbTasks; i++) {
        
        bool found = false;
        for(int j=0; j<NbTasks && !found; j++) {
            if (Tasks[j].succs->find(i+1) != Tasks[j].succs->end()) {
                found = true;
            }
        }
        
        if(!found) {
            printf("Task %d Has No Antecessors, ", i+1);
            printf("Problem Not Feasible.\n");
            exit(0);
        }
    }
    
    
	return 0;
}

/**
 * Show the read from file parameters
 */
void Print_Params()
{



    
    
	fprintf( out, "\nNbTasks = %d;\n"
           "NbRsrcs = %d;\n", NbTasks, NbRsrcs);
	fprintf( out, "Capacity = [ ");
    int q=0;
	for(q=0; q<NbRsrcs-1; q++)
		fprintf( out, "%d, ", Capacity[q]);
    fprintf( out, "%d ", Capacity[q]);
	fprintf( out, "];\n\n");
    
	std::set<int>::iterator it;
	std::set<int>::iterator itEnd;
    
	fprintf( out, "Tasks = {\n");
	for(int i=0; i<NbTasks; i++) {
		fprintf( out, "  < %d, %d, [ ", Tasks[i].id, Tasks[i].pt);
        
		int j=0;
		while(j<NbRsrcs-1)
			fprintf( out, "%d, ", Tasks[i].dmds[j++]);
		fprintf( out, "%d ], { ", Tasks[i].dmds[j]);
        
		if(Tasks[i].succs->size() > 0) {
			it = Tasks[i].succs->begin();
			itEnd = Tasks[i].succs->end();
			itEnd--;
			while(it != itEnd)
				fprintf( out, "%d, ", (*it++));
			fprintf( out, "%d }", (*it));
		} else
			fprintf( out, "}");
        
		fprintf( out, " >,\n");
	}
	fprintf( out, "};\n\n");
    
} /* Print Read Parameters */

/**
 * Free the memory used in data structures
 */
void Free()
{
    
	if ( Capacity ) free(Capacity);
	if ( Tasks ) {
		for(int i=0; i<NbTasks; i++) {
			if(Tasks[i].succs) delete Tasks[i].succs;
			if(Tasks[i].dmds) free(Tasks[i].dmds);
		}
		free(Tasks);
	}
    
    fclose (out);
}

/**
 * Calculate the predecessors for each task
 */
void Predecessors()
{
    
	std::set<int>::iterator it;
	std::set<int>::iterator itEnd;
    
	for(int k=0;k<NbTasks;k++)
		Tasks[k].preds = new std::set<int>();
    
	for(int k=0;k<NbTasks;k++) {
        
		if(Tasks[k].succs->size() > 0) {
			it = Tasks[k].succs->begin();
			itEnd = Tasks[k].succs->end();
            
			itEnd--;
			while(it != itEnd) {
				Tasks[(*it++)-1].preds->insert(Tasks[k].id);
			}
			Tasks[(*it)-1].preds->insert(Tasks[k].id);
		}
	}
    
}

/**
 * Prints the usage string to stderr and exits.
 */
void Usage(char *opt)
{
    
	printf("\nUsage:\n"
           "\t%s <filetype> <input filename> -t <threads number> -o <output filename>\n"
           "\n\n\tfiletype\t -c to Cplex input\n"
           "\t\t\t -p to Psplib input\n\n"
           "\t\t\t -u to CUClasthal input\n\n"
           "\tfilename\t file name\n"
           "\t\t\t threads default: 2\n\n", opt);
    
	exit(1);
    
}

/**
 * Parse the comand line arguments and set global variables
 */
void Parse_Arguments(int argc, char **argv)
{
	int op;
    
    OutputFileName = new char [ 20 ];
    sprintf( OutputFileName, "out.txt" );
    
	while ((op = getopt(argc, argv, "c:p:u:t:o:")) != -1)
	{
		switch (op)
		{
			case 'c':
                FileType = 1;
                FileName = optarg;
                break;
                
			case 'p':
                FileType = 2;
                FileName = optarg;
                break;
            case 't':
                NbThreads = atoi(optarg);
                break;
            case 'u':
                FileType = 3;
                FileName = optarg;
                break;
            case 'o':
                OutputFileName = optarg;
                break;
			default:
                Usage(argv[0]);
		}
	}
    
}

/*
 * Output operator to the Struct Node
 */
ostream &operator << ( std::ostream& ostrm, Node *No)
{
	
    ostrm << "Lower Bound    = [ " << No->LB << " ]\n";
    ostrm << "Schedule      " << No->PS;
    ostrm << "Processing    " << No->S;
    ostrm << "Cut Set       " << No->C;
    ostrm << "Final Times   " << No->F;
    ostrm << "Early Times   " << No->s;
    
	return ostrm;
}

/*
 * Output operator to the std::vector<int>
 */
ostream &operator << ( std::ostream& ostrm, vector<int> &list)
{
    
	ostrm << " = [ ";
	for ( unsigned int w = 0 ; w < list.size() ; w++ )
    {
		if (list[ w ] != inf) ostrm << list[ w ] << " ";
        else ostrm << "inf ";
    }
	ostrm << "]" << std::endl;
    
    
	return ostrm;
}

/*
 * Output operator to the std::set<int>
 */
ostream &operator << ( std::ostream& ostrm, set<int> &list)
{
    
	std::set<int>::iterator it;
	ostrm << " = [ ";
	for(it = list.begin(); it != list.end(); it++)
		ostrm << (*it) << " ";
	ostrm << "]" << std::endl;
    
	return ostrm;
}


